home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Visual Cafe 3
/
Visual Cafe 3.ISO
/
Vcafe
/
Source.bin
/
Matrix.java
< prev
next >
Wrap
Text File
|
1998-09-16
|
17KB
|
661 lines
package symantec.itools.awt;
import java.util.ResourceBundle;
// ===================================================================================
// = Revision History
// ===================================================================================
// Matrix
// This class implements a sparse matrix of objects
//
// 03/20/97 RKM Made the class public as per customer request
// Removed bogus debugging code
// Removed compaction of empty rows code
// 03/27/97 RKM Made class final (this class is not made to be extended)
// Followed example of Vector, and added JavaDoc, throws, & synchronized
// Made final
// Tried to make some sense of protection on methods & members
// 03/28/97 RKM Un-privitized members
// 05/02/97 RKM Fixed removeRow - made it actually work
// 05/02/97 RKM Fixed insertRow - one of the loops was not checking for null
// 05/13/97 TNM Added new interface CompareFuncCB to fix MultiList to not lose selection when sorting
// 05/30/97 RKM Moved CompareFunc interface into it's own file, at compiler's request
// 07/19/97 LAB Moved CompareFuncCB interface into it's own file, at compiler's request
// 07/23/97 CAR added java.io.Serializable interface
// 09/16/98 MSH Fixed insertRow - it now works when inserting a row at row 0 (#55390)
// Removed references to chicken-blood in the comments
/**
* This class implements a sparse matrix of objects.
* @version 1.0, Nov 26, 1996
* @author Symantec
*/
public final class Matrix implements java.io.Serializable
{
//--------------------------------------------------
// public constructors
//--------------------------------------------------
/**
* Constructs an empty matrix.
*/
public Matrix()
{
rowHead = this;
errors = ResourceBundle.getBundle("symantec.itools.resources.ErrorsBundle");
}
//--------------------------------------------------
// private constructors
//--------------------------------------------------
private Matrix(int r, int c, Object obj)
{
this(r, c, obj, null);
}
private Matrix(int r, int c, Object obj, Matrix rh, Matrix nr, Matrix ne)
{
errors = ResourceBundle.getBundle("symantec.itools.resources.ErrorsBundle");
if (rh == null)
{
if (c != 0)
{
rowHead = new Matrix(r, 0, null, null, nr, this);
}
else
{
rowHead = this;
}
}
else
{
rowHead = rh;
}
row = r;
col = c;
o = obj;
nextRow = nr;
nextElt = ne;
}
private Matrix(int r, int c, Object obj, Matrix nr, Matrix ne)
{
this(r, c, obj, null, nr, ne);
}
private Matrix(int r, int c, Object obj, Matrix nr)
{
this(r, c, obj, null, nr, null);
}
//--------------------------------------------------
// public methods
//--------------------------------------------------
/**
* Adds the given element to this matrix at the specified row and column.
* @param r the row of the element to be added
* @param c the column of the element to added
* @param o the element to be added
* @exception IllegalArgumentException if an element is already allocated
* at [r,c]
* @see #updateElement
* @see #removeElementAt
*/
public synchronized void addElement(int r, int c, Object o)
throws IllegalArgumentException
{
//find the correct row
Matrix m = nearest(r, c);
if (m.row != r)
{
m.setNextRow(new Matrix(r, c, o, m.nextRow).rowHead);
return;
}
//m must equal row
if (c == m.col && c == 0)
{
if (m.o != null)
{
//exception - should call update
throw new IllegalArgumentException(errors.getString("ElementAlreadyInMatrix"));
}
else
{
m.o = o;
return;
}
}
m.nextElt = new Matrix(r, c, o, m.rowHead, m.nextRow, m.nextElt);
}
/**
* Adds or updates the element at the specified row and column, as needed.
* @param r the row of the element to be updated
* @param c the column of the element to updated
* @param o the new element
* @see #addElement
* @see #removeElementAt
*/
public synchronized void updateElement(int r, int c, Object obj)
{
Matrix m = nearest(r, c);
try
{
if (m == null)
{
//first element in matrix
addElement(r, c, obj);
}
else if (m.row != r || m.col != c)
{
m.addElement(r, c, obj);
}
else
{
//must be the element
m.o = obj;
}
}
catch(IllegalArgumentException iae)
{
iae.printStackTrace();
}
}
/**
* Removes all elements of the matrix. The matrix becomes empty.
* @see #addElement
* @see #removeElementAt
*/
public synchronized void removeAllElements()
{
nextRow = null;
nextElt = null;
o = null;
}
/**
* Returns the element at the specified row and column.
* @param r the row of the element to return
* @param c the column of the element to return
* @return the element at [r,c]
* @exception ArrayIndexOutOfBoundsException if an invalid
* row and/or column was given
*/
public synchronized Object elementAt(int r, int c)
throws ArrayIndexOutOfBoundsException
{
Matrix m = nearest(r, c);
if (m == null || m.row != r || m.col != c || m.o == null){
Object[] args = { new Integer(r), new Integer(c) };
throw new ArrayIndexOutOfBoundsException(java.text.MessageFormat.format(errors.getString("ElementNotInMatrix"), args));
}
return m.o;
}
/**
* Deletes the element at the specified row and column.
* @param r the row of the element to remove
* @param c the column of the element to remove
* @exception ArrayIndexOutOfBoundsException if an invalid
* row and/or column was given
*/
public synchronized void removeElementAt(int r, int c)
throws ArrayIndexOutOfBoundsException
{
Matrix m = nearest(r, c);
if (m == null || m.row != r || m.col != c) {
Object[] args = { new Integer(r), new Integer(c) };
throw new ArrayIndexOutOfBoundsException(java.text.MessageFormat.format(errors.getString("ElementNotInMatrix"), args));
}
if (c == 0)
{
m.o = null;
return;
}
Matrix prev = m = m.rowHead;
while(m.col != c)
{
prev = m;
m = m.nextElt;
}
prev.nextElt = m.nextElt;
}
/**
* Deletes all elements on the specified row.
* @param r the row of the elements to remove
* @see #insertRow
* @see #removeElementAt
*/
public synchronized void removeRow(int r)
{
//Removing zero is a special case, essentially we have to change this
if (r == 0)
{
this.o = null;
this.nextElt = null;
if (this.nextRow != null)
{
//Remove new zero elem from the row list and assign its data into this
Matrix newZeroElem = this.nextRow;
this.nextRow = newZeroElem.nextRow;
this.nextElt = newZeroElem.nextElt;
this.row = newZeroElem.row;
this.col = newZeroElem.col;
this.o = newZeroElem.o;
//Hook up rowHeads of the elements in zero elem (since it's now this)
{
Matrix elemMatrix = this.nextElt;
while (elemMatrix != null)
{
elemMatrix.rowHead = this;
elemMatrix = elemMatrix.nextElt;
}
}
//Decrement row of all matrixs
Matrix stepMatrix = this;
while (stepMatrix != null)
{
stepMatrix.updateRowNum(stepMatrix.row - 1);
stepMatrix = stepMatrix.nextRow;
}
}
}
else
{
//Find the matrix that comes before the row, if it exists
Matrix stepMatrix = this.nextRow;
Matrix lastRow = this;
while (stepMatrix != null && stepMatrix.row < r)
{
lastRow = stepMatrix;
stepMatrix = stepMatrix.nextRow;
}
if (stepMatrix != null)
{
//We have an explicit row matrix
if (stepMatrix.row == r)
{
//Skip it in the chain
lastRow.nextRow = stepMatrix.nextRow;
stepMatrix.o = null;
stepMatrix.nextElt = null;
//Advance a row (number changing purposes)
stepMatrix = stepMatrix.nextRow;
}
//Change the row numbers of all the remaining rows
while (stepMatrix != null)
{
stepMatrix.updateRowNum(stepMatrix.row - 1);
stepMatrix = stepMatrix.nextRow;
}
}
}
/* RKM Was
Matrix m = nearest(r, 0);
if (m.row == r)
{
m = m.rowHead;
m.o = null;
m.nextElt = null;
}
*/
}
/**
* Inserts a new row at the given location.
* It does this by incrementing the row number of all elements with
* row indexes >= given row number.
* @param r the number of the row to insert
* @see #removeRow
*/
public synchronized void insertRow(int r)
{
Matrix m, n;
if (r == 0)
{
m = new Matrix(); // make a new matrix and copy current item at 0,0
m.rowHead = m;
m.nextRow = this.nextRow;
m.nextElt = this.nextElt;
m.o = this.o;
this.nextRow = m; // set up this to be the new "origin" item
this.nextElt = null;
this.o = null;
m = this; // need to do this so row re-numbering happens
}
else
{
m = nearest(r-1, 0);
n = new Matrix(r, 0, null, m.nextRow);
m.setNextRow(n);
m = n;
}
if (m.nextRow.row == r)
{
//slip and increment row numbers
m = m.nextRow;
while(m != null)
{
m.updateRowNum(++r);
m = m.nextRow;
if (m != null && m.row != r) return;
}
}
}
/**
* Sorts all rows into ascending order.
* It does this by comparing elements at the given
* column number using the provided CompareFunc.
* @param f compares two objects and determines which one is less than the other
* @param c the column number of elements to compare
*/
public synchronized void sort(CompareFunc f, int c)
{
boolean first = true;
Matrix m = this,
n = null;
while(m != null)
{
n = findLeast(f, m, c, first);
if (n != null)
{
if (m.row == 0 && first)
{
first = false;
if(f instanceof CompareFuncCB)
((CompareFuncCB)f).callBackSwap(m, n.nextRow);
swapRows(n);
m = this;
continue;
}
else
{
if(f instanceof CompareFuncCB)
((CompareFuncCB)f).callBackSwap(m.nextRow, n.nextRow);
swapRows(m, n);
}
}
if (first)
{
first = false;
continue;
}
m = m.nextRow;
}
}
/**
* Prints the specified row to System.out.
* This can be handy for debugging purposes.
* @param r the row to print
*/
public synchronized void printRow(int r)
{
Matrix m = nearest(r, 0);
if (m.row != r)
{
m = m.nextRow;
if (m.row != r)
{
Object[] args = { new Integer(r) };
System.out.println(java.text.MessageFormat.format(errors.getString("RowNotInMatrix"), args));
return;
}
}
System.out.println("-------- Printing row " + r + " ----------");
while(m != null)
{
System.out.println("Row=" + m.row + " Col=" + m.col + " value=" + m.o);
m = m.nextElt;
}
}
/**
* Returns the number of rows in the matrix.
*/
public synchronized int rows()
{
Matrix m = this;
while(m.nextRow != null)
{
m = m.nextRow;
}
return (m.nextElt == null && m.o == null ? m.row : m.row+1);
}
//only call on row head
private synchronized void updateRowNum(int r)
{
Matrix m = this;
while(m != null)
{
m.row = r;
m = m.nextElt;
}
}
/**
* Returns an enumeration of all the elements. Use the enumeration methods
* of the returned object to fetch the elements sequentially.
*/
public synchronized MatrixEnumeration elements()
{
return new MatrixEnumeration(this);
}
/**
* Returns a string representation of this component.
* This is a standard Java AWT method which gets called to generate
* a string that represents this component.
*
* @return a meaningful string about this object
*/
public synchronized String toString()
{
return "Matrix: row=" + row + " col=" + col + " o=" + o;
}
//--------------------------------------------------
// private members
//--------------------------------------------------
private synchronized Matrix nearest(int r, int c)
{
//find the correct row
Matrix m = this;
while (r > m.row)
{
if (m.nextRow != null && m.nextRow.row <= r)
{
//further down pike so keep climbing
m = m.nextRow;
}
else
{
return m;
}
}
//m must equal row
while (m.nextElt != null && c >= m.nextElt.col)
{
//further down the line
m = m.nextElt;
}
return m;
}
private synchronized void setRowHead()
{
Matrix m = nextElt;
Matrix h = this;
while (m != null)
{
m.rowHead = h;
m = m.nextElt;
}
}
private synchronized void setNextRow(Matrix nr)
{
Matrix m = this;
while(m != null)
{
m.nextRow = nr;
m = m.nextElt;
}
}
//m1 & m2 preceed the two rows to be switched.
private synchronized void swapRows(Matrix p1, Matrix p2)
{
Matrix t1 = p1.nextRow;
Matrix t1NextRow = t1.nextRow;
Matrix t2 = p2.nextRow;
Matrix t2NextRow = t2.nextRow;
p1.setNextRow(t2);
p2.setNextRow(t1);
if (p2 == t1)
{
t2.setNextRow(t1);
}
else
{
t2.setNextRow(t1NextRow);
}
t1.setNextRow(t2NextRow);
int t1Row = t1.row;
t1.updateRowNum(t2.row);
t2.updateRowNum(t1Row);
}
//swap the current row (must be the first) with the row following m2
private synchronized void swapRows(Matrix m2)
{
Matrix t2 = m2.nextRow;
Matrix t1 = new Matrix(-1, t2.col, o, null, nextElt);
m2.rowHead.setNextRow(t1);
t1.setNextRow(t2.nextRow);
t1.updateRowNum(t2.row);
t1.setRowHead();
//fixup root node (that is this)
nextElt = t2.nextElt;
o = t2.o;
setNextRow(nextRow); //this.nextRow never changed so can use for update
updateRowNum(0);
setRowHead();
}
private synchronized Matrix findLeast(CompareFunc f, Matrix m, int c, boolean first)
{
//m is row previous to one to be compared to when m.row != 0
if (!first)
m = m.nextRow;
if(m == null || m.nextRow == null)
return null;
Matrix n = m.nextRow.rowHead;
Matrix prevToN = m.rowHead;
Matrix prevToLeast = null;
m = m.nearest(m.row, c);
while (n != null)
{
n = n.nearest(n.row, c);
if (n.col != c)
{
//no item for column on next row so keep searching
prevToN = n.rowHead;
n = n.nextRow;
continue;
}
else if (m.col != c)
{
//no item for first column so automatically sent down
m = n;
prevToLeast = prevToN;
continue;
}
if (f.lessThan(n.o, m.o))
{
//n < m so put n in for least
m = n;
prevToLeast = prevToN;
}
prevToN = n.rowHead;
n = n.nextRow;
}
return prevToLeast;
}
/**
* Error strings.
*/
transient protected ResourceBundle errors;
//--------------------------------------------------
// private members
//--------------------------------------------------
Matrix rowHead;
Matrix nextRow;
Matrix nextElt;
int row;
int col;
Object o;
}